package SwordFingerOffer;

import java.util.function.DoublePredicate;

public class Q10_2_FlogJump {

    //青蛙跳台阶
    //一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
    //求该青蛙跳上一个 n 级的台阶总共有多少种跳法

    //暴力递归
    public int numWays(int n) {
        if (n < 0){
            return 0;
        }

        return process(0, n);
    }

    // index位置 n是台阶数
    public int process(int index, int n){

        if (index > n){
            return 0;
        }
        if (index == n){
            return 1;
        }
        //跳一层
        int oneWays = process(index + 1, n);
        //跳两层
        int twoWays = process(index + 2, n);

        return oneWays + twoWays;
    }

    //动态规划
    public static int numWays_2(int n) {
        if (n < 3){
            return n;
        }
        int[] dp = new int[n + 1];
        dp[n] = 1;
        dp[n - 1] = 1;

        for (int i = n - 2; i >= 0; i--) {
            //题目要求
            dp[i] = (dp[i + 1] + dp[i + 2]) % 1000000007;
        }

        return dp[0];

    }


    public static void main(String[] args) {
        int i = numWays_2(3);
        System.out.println(i);
    }
}
